﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//二叉搜索树与双向链表
//https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
class Solution {
public:
	TreeNode* head = nullptr;
	TreeNode* prev = nullptr;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        //遍历二叉树 转换成链表
		//left->prev right->next
		//中序遍历
		if(!pRootOfTree) return pRootOfTree;
		//左子树开始
		Convert(pRootOfTree->left);

		//如果前驱为空则记录叶节点信息
		if(!prev)
		{
			prev = pRootOfTree;
			head = pRootOfTree;
		}
		else //前驱不为空 则构建连接关系
		{
			//当前节点的前驱指针 指向上一个节点(按照中序遍历的顺序)
			pRootOfTree->left = prev;
			//前驱节点的下一个就是当前节点
			prev->right = pRootOfTree;
			//记录当前节点为前驱节点 方便中序遍历的下一个节点连接
			prev = pRootOfTree;
		}
		//右子树中连接
		Convert(pRootOfTree->right);
		return head;
    }
};

 //二叉树的最近公共祖先
 //https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //如果当前节点就是其中一个子节点 则该节点的上一个就是祖先
        if(!root || root == p || root == q) return root;

        //当p和q在同一颗子树时 l和r的返回值中必定有一个空 则会返回非空的那一个节点
        TreeNode* l = lowestCommonAncestor(root->left,p,q);
        TreeNode* r = lowestCommonAncestor(root->right,p,q);
        //如果l和r有一个为空 则当前节点的父子节点肯定在另一颗子树中
        //因为当root == p || root == q时会返回 否则会一直递归到空
        //如果返回为空 则另一边一旦找到了一个q或p则该节点就是祖先
        //只要是一边没有符合条件的节点 就会在另一颗子树中继续查找
        //当l和r都不为空，则表示p和q分别在左右子树 此时root就是祖先
        return (l && r)?root:(l?l:r);
    }
};

